package run.siyuan.jdk.漫画算法.树;

/**
 * @ClassName ArrayTree
 * @Description TODO 基于数组实现二叉树,基本功能实现，但需要考虑后期扩容
 * @Author siyuan
 * @Date 2023/4/8 16:35
 */
public class ArrayBinaryTree {

    private int[] array;
    private int size;

    private int rootData;
    private int rootIndex;

    public ArrayBinaryTree(int capacity) {
        this.array = new int[capacity];
        this.size = 0;
    }

    public static void main(String[] args) {
        ArrayBinaryTree tree = new ArrayBinaryTree(10);
        tree.insert(6);
        tree.insert(4);
        tree.insert(8);
        tree.insert(2);
        tree.insert(5);
        tree.insert(9);
        tree.insert(3);
        tree.insert(7);
        tree.insert(100);
//        tree.insert(101);
        tree.show();
    }

    /**
     * 插入
     *
     * @param element
     */
    public void insert(int element) {
        // 扩容
        checkResize(size);

        if (size == 0) {
            this.array[size] = element;
            rootData = element;
            rootIndex = size;
        } else if (size > 0) {
            int index = getParent(element, rootIndex);
            this.array[index] = element;
        }
        size++;
    }

    /**
     * 查找父节点对应的下标
     *
     * @param element 元素
     * @param index   下标
     * @return 下标
     */
    private int getParent(int element, int index) {
        int parentEle = this.array[index];
        if (element < parentEle) {
            // 左结点
            index = 2 * index + 1;
            checkResize(index);
            int leftEle = this.array[index];
            if (leftEle == 0) {
                return index;
            }
//            if (leftEle != 0 && element < leftEle) {
//                return getParent(element, index);
//            }
        } else if (element > parentEle) {
            // 右节点
            index = 2 * index + 2;
            checkResize(index);
            int rightELe = this.array[index];
            if (rightELe == 0) {
                return index;
            }
//            if (rightELe != 0 && element > rightELe) {
//                return getParent(element, index);
//            }
        }
        return getParent(element, index);
    }

    /**
     * 校验是否需要扩容
     * @param index
     */
    public void checkResize(int index){
        if (index >= this.array.length) {
            resize();
        }
    }

    /**
     * 扩容原来的 1.5 倍
     */
    public void resize() {
        int length = this.array.length >> 1;
        length = length + this.array.length;
        int[] array = new int[length];
        for (int i = 0; i < this.array.length; i++) {
            array[i] = this.array[i];
        }
        this.array = array;
    }

    /**
     * 打印
     */
    public void show() {
        for (int i = 0; i < this.array.length; i++) {
            System.out.printf("%d\t%d\n", i, this.array[i]);
        }
    }

}
